// 给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
// 每次转换只能改变一个字母。
// 转换过程中的中间单词必须是字典中的单词。

// 说明:
// 如果不存在这样的转换序列，返回 0。
// 所有单词具有相同的长度。
// 所有单词只由小写字母组成。
// 字典中不存在重复的单词。
// 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。


const ladderLength = function (beginWord: string, endWord: string, wordList: string[]): number {
    const wordSet = new Set<string>(wordList); // 声明一个哈希集合存储单词
    const visited = new Set<string>([beginWord]); // 声明一个哈希集合判断元素是否被访问过
    if (!wordSet.has(endWord)) {
        return 0;
    }
    let step: number = 1;// 步长
    const queue: string[] = [beginWord];// 广度优先遍历队列
    while (queue.length > 0) {
        let currLen = queue.length;// 当前元素长度
        for (let i = 0; i < currLen; i++) {
            let currWord = queue.shift()!;// 当前单词
            // 替换每个单词的位置
            for (let j = 0; j < currWord.length; j++) {
                // 用每个字母来尝试
                for (let letterCode = 97; letterCode <= 122; letterCode++) {
                    let newWord = currWord.slice(0, j) + String.fromCharCode(letterCode) + currWord.slice(j + 1);
                    // 如果单词表中出现了
                    if (wordSet.has(newWord)) {
                        // 当符合终点词，直接返回步长+1
                        if (newWord === endWord) {
                            return step + 1;
                        }
                        // 没有访问过的元素才有资格入队
                        if (!visited.has(newWord)) {
                            visited.add(newWord);
                            queue.push(newWord);
                        }
                    }
                }
            }
        }
        // 步长+1
        step++;
    }
    return 0;
};



// 这道题的代码书写难度较大，也不好想到，实际上是使用图论的思路来求解的，可以作为一个例题来学习
// 首先记一个结论，无向图中两个顶点之间的最短路径的长度，可以通过广度优先遍历得到
// 为什么 BFS 得到的路径最短？可以把起点和终点所在的路径拉直来看，两点之间线段最短
// 这里需要两个哈希集，可以加快访问的速度：
// 一个哈希集用于存储单词表的单词，另一个哈希表用于存储访问过的单词
// 理解了上述前提之后，我们要做的事情其实比较直接
// 从起点词出发，每次变动一个字母，经过 n 次变换，变成终点词，希望 n 尽量小
// 我们需要找出邻接关系，比如hit它变一个字母会变成_it、h_t、hi_形式的单词
// 在这个搜寻的过程中，比较直白的就是用26个字母去换出新词
// 然后看这个新词是否存在于单词表，如果存在，就找到了一个下一层的转换词
// 同时，要避免重复访问，访问过的元素要加入访问集合，如果出现回路，只会徒增转换的长度
// 当队列为空时，BFS结束，如果始终没有遇到终点词，没有路径通往终点，返回 0